|
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number. Every graph with vertices has book thickness at most , and this formula gives the exact book thickness for complete graphs. The graphs with book thickness one are the outerplanar graphs. The graphs with book thickness at most two are the subhamiltonian graphs, which are always planar; more generally, every planar graph has book thickness at most four. All minor-closed graph families, and in particular the graphs with bounded treewidth or bounded genus, also have bounded book thickness. It is NP-hard to determine the exact book thickness of a given graph, with or without knowing a fixed vertex ordering along the spine of the book. One of the original motivations for studying book embeddings involved applications in VLSI design, in which the vertices of a book embedding represent components of a circuit and the wires represent connections between them. Book embedding also has applications in graph drawing, where two of the standard visualization styles for graphs, arc diagrams and circular layouts, can be constructed using book embeddings. In transportation planning, the different sources and destinations of foot and vehicle traffic that meet and interact at a traffic light can be modeled mathematically as the vertices of a graph, with edges connecting different source-destination pairs, and a book embedding of this graph can be used to design a schedule that lets all the traffic move across the intersection with as few signal phases as possible. In bioinformatics problems involving the folding structure of RNA, single-page book embeddings represent classical forms of nucleic acid secondary structure, and two-page book embeddings represent pseudoknots. Other applications of book embeddings include abstract algebra and knot theory. There are several open problems concerning book thickness. It is unknown whether the book thickness of arbitrary graphs can be bounded by a function of the book thickness of their subdivisions. Testing the existence of a three-page book embedding of a graph, given a fixed ordering of the vertices along the spine of the embedding, has unknown computational complexity: it is neither known to be solvable in polynomial time nor known to be NP-hard. And, although every planar graph has book thickness at most four, it is unknown whether whether there exists a planar graph whose book thickness is exactly four. ==History== The notion of a book, as a topological space, was defined by C. A. Persinger and Gail Atneosen in the 1960s.〔〔. See also .〕 Atneosen already considered embeddings of graphs in books, using the standard concept of an ambedding of a graph into a topological space, in which the vertices are represented by distinct points, each edge is represented as a curve, and the only way that two edges can intersect is for them to meet at a common endpoint. However, the formal concept of book embeddings of graphs was formulated later, by Paul C. Kainen and L. Taylor Ollman in the early 1970s. In their formulation, Kainen and Ollman imposed some additional constraints on the way the graph is allowed to be embedded, that were not present in the earlier work of Atneosen: the graph's vertices must be placed along the spine of the book, and each edge must lie in a single page.〔.〕〔.〕 Important milestones in the later development of book embeddings include the proof by Mihalis Yannakakis in the late 1980s that planar graphs have book thickness at most four,〔〔 and the discovery in the late 1990s of close connections between book embeddings and bioinformatics.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「book embedding」の詳細全文を読む スポンサード リンク
|